package leetcode_acm.leetcode_1;

import sun.reflect.generics.tree.Tree;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月11日 13:41
 */
public class ConstructMaximumBinaryTree {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums,0,nums.length-1);
    }

    private TreeNode construct(int[] nums,int begin,int end){
        if(begin > end){
            return null;
        }
        //遍历从[begin,end上的最大值]
        //先寻找最大值
        int max = nums[begin];
        int maxIndex = begin;
        for(int i = begin+1;i<=end;i++){
            if(max < nums[begin]){
                maxIndex = i;
                max = nums[begin];
            }
        }
        TreeNode root = new TreeNode(max);
        //构造左子树
        root.left = construct(nums,begin,maxIndex-1);
        root.right = construct(nums,maxIndex+1,end);
        return root;
    }

}
